/*oOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoO*/
/*
Authors: Ram Ovadia 201374022 and Lior Fass 300069705
Project: HW Assignment 3 
Description: This is the implementation of the double linked list module used in the project.  
*/
/*oOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoOoO*/

#include "List.h"

/*
* Allocates memory for List struct.     
* 
* Input:
* -----
* None     
*
* Output:
* -----
* Return Value:
* Pointer to allocated memory for list, or NULL if allocation failed. 
*/
List *List_create()
{
	return (List *)calloc(1, sizeof(List));
}

/*
* Destorys list. deallocated memory of List struct and all ListNodes.      
* 
* Input:
* -----
* list - pointer to List to be destoryed.      
*
* Output:
* -----
* Return Value:
* 0 - successful
* 1 - invalid list argument.  
*/
int List_destroy(List *list, Free_value_func free_value_func)
{
	if (list != NULL)
	{
		LIST_FOREACH(list, first, next, cur) {
			if(cur->prev) {
				free(cur->prev);
			}
			if (free_value_func!=NULL)
			{
				free_value_func(cur->value);
			}
		}
		free(list->last);
		free(list);
		return 0;
	}
	else
	{
		printf("bad list argument in List_destroy\r\n");
		return 1;
	}
}

/*
* Clears all values in all ListNodes of list. 
* calls free_value_func for specific freeing routines (especially for nested structs) 
* if not supllied, all ListNodes value will point to NULL.      
* 
* Input:
* -----
* list - pointer to List to be cleard.      
*
* Output:
* -----
* Return Value:
* 0 - successful
* 1 - invalid list argument.  
*/
int List_clear(List *list, Free_value_func free_value_func)
{
	if (list != NULL)
	{
		LIST_FOREACH(list, first, next, cur) {
			if(cur->prev) {
				free(cur->prev);
			}
			if (free_value_func!=NULL)
			{
				free_value_func(cur->value);
			}
		}
		free(list->last);
		list->first=NULL;
		list->last=NULL;
		list->count=0;
		return 0;
	}
	else
	{
		printf("bad list argument in List_clear\r\n");
		return 1;
	}
}

/*
* Creates a new ListNode, and adds value to the end of the List.      
* 
* Input:
* -----
* list - pointer to List to which we want to add a new node.
* value - pointer to value to be pointed to by the new node. 
*
* Output:
* -----
* Return Value:
* 0 - successful
* 1 - invalid list argument. or failed allocation.  
*/
int List_push(List *list, void *value)
{
	if (list !=NULL)
	{
		ListNode *node = (ListNode *)calloc(1, sizeof(ListNode));
		if (node == NULL)
		{
			printf("failed memory allocation in list_push\n");
			return 1;
		}
		node->value = value;

		if(list->last == NULL) {
			list->first = node;
			list->last = node;
		} else {
			list->last->next = node;
			node->prev = list->last;
			list->last = node;
		}

		list->count++;
		return 0;
	}
	else 
	{
		printf("bad list argument in List_push\r\n");
		return 1;
	}
}

/*
* Returns value held by the last ListNode in the list, and removes that ListNode from the List.        
* 
* Input:
* -----
* list - pointer to List from which we want to pop a new node. 
*
* Output:
* -----
* Return Value:
* if successful returns a pointer to the value held by the last ListNode in the List, otherwise returns NULL. 
*/
void *List_pop(List *list)
{
	if (list != NULL)
	{
		ListNode *node = list->last;
		return node != NULL ? List_remove(list, node) : NULL;
	}
	else
	{
		printf("bad list argument in List_pop\r\n");
		return NULL;
	}
}

/*
* removes given node from list. assumes node is in list.        
* 
* Input:
* -----
* list - pointer to List from which we want to remove node. 
* node - pointer to ListNode in list which we want to remove. 
*
* Output:
* -----
* Return Value:
* if successful returns a pointer to the value held by the removed ListNode in the List, otherwise returns NULL. 
*/
void *List_remove(List *list, ListNode *node)
{
	if ((list != NULL) && (node != NULL))
	{
		void *result = NULL;

		if(node == list->first && node == list->last) {return
			list->first = NULL;
		list->last = NULL;
		} else if(node == list->first) {
			list->first = node->next;
			list->first->prev = NULL;
		} else if (node == list->last) {
			list->last = node->prev;
			list->last->next = NULL;
		} else {
			ListNode *after = node->next;
			ListNode *before = node->prev;
			after->prev = before;
			before->next = after;
		}

		list->count--;
		result = node->value;
		free(node);
		return result;
	}
	else
	{
		printf("bad arguments in List_remove\r\n");
		return NULL;
	}
}

/*
* rearranges items in the ListNodes of list into a single preallocated array.
* Array items are copies of the original items, and are not linked         
* 
* Input:
* -----
* list - pointer to List from which we want create array.
* element_Array - pointer to a preallocated memmory that can hold all the items held by the the ListNodes of list. 
* size_of_element - size in bytes of each item held ny ListNodes in list. must all be of the same size. 
*
* Output:
* -----
* Return Value:
* 0 - successful, element_array will hold all items in list.
* 1 - unsuccessful. 
*/
int List_to_array(List *list, void * element_array, int size_of_element)
{
	if ((list != NULL) && (element_array !=NULL) && (size_of_element > 0))
	{
		int i = 0;
		LIST_FOREACH(list, first, next, cur){
			memcpy(((char *)element_array+i*size_of_element), cur->value, size_of_element);
			i++;
		}
		return 0;
	}
	else
	{
		printf("bad arguments in List_to_array\r\n");
		return 1;
	}
}

void List_print(List *list, Print_value_func print_value_func)
{
	LIST_FOREACH(list, first, next, cur){
		print_value_func(cur->value);
		printf(", ");
	}
	printf("\r\n");
}

void *List_find(List *list, Comp_value_func comp_value_func, void *element)
{
	if (list!=NULL)
	{
		LIST_FOREACH(list, first, next, cur){
			if (comp_value_func(cur->value, element) == 0)
			{
				return cur->value;
			}
		}
		return NULL;
	}
	else
	{
		printf("bad arguments in List_find\r\n");
		return NULL;
	}
}

/*
* push ListNode A pointed to by pNodeA after ListNode B pointed to by pNodeB. Both are originally in mail_list. 
* 
* Input:
* -----
* pNodeA/B - pointer to ListNodes in mail_list. A will be pulled and replaced following B.    
*
* Output:
* -----
* Return Value:
* None. mail_list will be rearranged. 
*/
void PushNodeAAfterNodeB(List *list, ListNode * pNodeA, ListNode * pNodeB)
{
	//PULL A OUT
	if (list->first == pNodeA)
	{
		list->first = (list->first)->next;
		(list->first)->prev = NULL;
	}
	else if (list->last == pNodeA)
	{
		list->last = pNodeA->prev;
		(list->last)->next = NULL;
	}
	else 
	{
		(pNodeA->prev)->next = pNodeA->next;
		(pNodeA->next)->prev = pNodeA->prev;
	}

	//INSERT A AFTER B
	if (pNodeB == NULL)
	{
		pNodeA->next = list->first;
		pNodeA->prev = NULL;
		(list->first)->prev = pNodeA;
		list->first = pNodeA;
	}
	else if (list->last == pNodeB)
	{
		pNodeB->next = pNodeA;
		pNodeA->next = NULL;
		pNodeA->prev = pNodeB;
		list->last = pNodeA;
	}
	else
	{
		pNodeA->next = pNodeB->next;
		pNodeA->prev = pNodeB;
		(pNodeB->next)->prev = pNodeA;
		pNodeB->next = pNodeA;
	}

	/*
	//Pull A out
	(pNodeA->prev)->next = pNodeA->next;
	if ((pNodeA->next) == NULL) //A is last
	list->last = pNodeA->prev;
	else
	(pNodeA->next)->prev = pNodeA->prev;

	//insert A after B
	if (pNodeB == NULL) // B is before first
	{
	pNodeA->prev = NULL;
	list->first->prev = pNodeA;
	pNodeA->next = list->first;
	list->first = pNodeA;
	}
	else
	{
	pNodeA->next=pNodeB->next;
	pNodeA->prev=pNodeB;
	(pNodeB->next)->prev = pNodeA;
	pNodeB->next = pNodeA;
	}
	*/
}

/*
* Implements insertion sort algorithm on mail_list. 
* 
* Input:
* -----
* None. 
*
* Output:
* -----
* Return Value:
* 0 if successful. mail_list will be rearranged. 
*/
int List_insert_sort(List *list, Comp_value_func comp_value_func) 
{
	if (list!=NULL && list->count > 0)
	{
		ListNode * currNode = list->first;
		ListNode * nextNode = currNode->next;
		ListNode * compNode = NULL;
		// zero or one element in list
		if(currNode == NULL || currNode->next == NULL)
			return 0;
		// more then one element
		while (nextNode != NULL)
		{
			compNode = nextNode->prev;
			currNode = nextNode;
			nextNode = nextNode->next;
			while ( (compNode != NULL) && (comp_value_func(currNode->value,compNode->value) < 0) )
				compNode = compNode->prev;
			PushNodeAAfterNodeB(list, currNode, compNode);
		}
		return 0;
	}
	return 1;
}

/*
* Reverses the order of Nodes in mail_list. 
* 
* Input:
* -----
* None
*
* Output:
* -----
* Return Value:
* None. mail_list will be reversed ordered. 
*/
int ReverseList(List *list)
{
	if (list != NULL)
	{
		ListNode *tempNode,*curNode; 
		tempNode = list->first;
		list->first = list->last;
		list->last = tempNode;
		curNode = list->first;
		while (curNode != NULL)
		{
			tempNode = curNode->next;
			curNode->next = curNode->prev;
			curNode->prev = tempNode;
			curNode = curNode->next;
		}
		return 0;
	}
	return 1;
}




